n=1000;
m=80;
w=[5,58,5,83,100,91,10,77,11,61,32,4,100,10,15,36,82,88,6,98,28,93,90,70,22,19,29,17,17,96,94,79,36,61,64,36,5,53,9,35,5,9,97,16,27,5,91,34,71,81,3,56,38,53,9,42,31,50,65,50,70,46,60,96,16,98,2,97,70,22,20,55,11,32,71,45,63,57,97,52,13,76,67,35,31,32,5,71,97,68,6,94,83,69,95,21,51,53,54,11,50,29,5,75,69,28,65,21,11,69,80,6,54,1,38,34,95,62,63,41,18,63,84,48,13,89,28,33,24,61,65,69,28,44,87,61,44,75,28,83,81,46,45,38,85,3,63,69,78,15,38,69,80,73,34,24,16,30,74,40,34,83,22,7,90,37,40,9,38,6,19,16,76,1,19,90,81,83,67,32,1,94,63,62,49,91,100,15,49,87,42,78,31,64,82,37,87,17,65,41,13,9,3,83,68,11,23,93,32,29,45,24,78,13,37,56,7,65,72,52,62,58,96,80,82,98,81,88,67,95,21,7,39,55,19,56,93,27,100,44,45,49,34,60,58,82,14,16,84,26,39,52,8,9,23,37,31,69,90,27,78,53,89,87,6,6,48,56,18,68,83,98,40,35,45,32,22,18,2,69,94,64,4,69,40,13,4,38,42,83,26,3,100,73,8,19,17,40,10,77,14,89,63,75,89,35,95,13,17,5,38,35,32,13,4,9,8,10,74,30,27,62,8,43,13,45,11,41,60,22,32,66,10,83,57,87,76,48,12,82,86,66,46,63,74,2,58,52,94,43,62,57,46,16,1,51,61,23,81,48,3,40,15,4,7,78,37,75,73,27,59,35,43,95,9,32,47,43,84,88,13,93,51,59,75,7,40,43,56,68,99,65,61,30,70,25,69,6,98,42,60,44,45,9,63,18,68,78,61,99,14,55,45,77,82,1,74,52,2,80,7,11,33,11,72,52,46,4,60,3,61,85,74,27,49,87,21,100,18,37,7,92,85,4,37,81,22,78,15,18,38,1,20,86,74,34,83,17,98,29,9,72,37,31,61,19,92,65,95,77,16,70,25,56,73,92,35,93,29,15,91,31,73,54,72,59,6,42,91,90,27,1,10,54,95,64,86,90,5,79,88,85,38,100,4,84,61,26,14,75,80,26,4,97,7,72,68,39,71,8,10,55,69,27,57,61,58,100,62,86,21,18,40,99,55,12,14,56,78,86,86,90,13,25,44,45,11,90,14,34,99,95,69,16,3,31,8,41,79,16,51,16,51,41,91,64,91,16,44,100,19,68,59,33,24,20,13,91,66,96,80,24,42,64,12,33,81,46,89,10,29,51,99,72,80,89,9,93,31,22,94,67,61,13,74,9,64,13,65,35,59,19,37,88,17,69,36,45,64,83,90,87,74,69,64,29,64,48,99,67,83,34,85,95,48,68,37,22,78,66,98,32,19,66,20,15,23,28,79,53,88,66,1,66,99,98,24,53,2,81,27,77,78,78,15,6,35,98,53,47,98,39,66,24,13,21,63,58,89,85,2,73,25,96,77,37,18,95,2,62,99,29,62,78,5,16,70,13,18,41,62,98,79,50,100,37,18,85,33,75,99,10,46,9,89,51,6,97,35,44,6,93,2,46,37,29,44,100,44,76,99,83,33,53,5,81,48,52,18,97,30,26,60,73,66,49,7,90,72,45,41,55,23,70,64,27,82,59,98,44,87,46,19,20,100,65,81,75,6,37,36,45,50,13,73,38,1,68,5,46,95,19,21,2,27,69,12,84,63,68,59,26,30,93,65,94,1,54,3,37,22,43,69,93,25,98,57,23,5,100,87,69,59,89,83,20,5,21,83,38,74,92,48,50,48,39,90,23,34,44,22,30,24,80,56,86,51,55,29,18,81,23,66,82,80,32,58,6,93,76,17,52,81,3,5,46,71,25,97,7,1,95,51,82,88,6,10,43,88,58,24,34,81,74,94,90,74,92,34,82,76,4,65,70,42,8,97,44,10,15,20,52,97,38,57,49,74,34,82,65,64,47,71,48,41,41,94,71,89,53,60,71,20,26,47,48,51,88,81,99,53,56,75,12,53,6,97,80,58,96,69,94,40,72,22,59,41,67,35,55,6,99,72,50,10,85,64,19,67,23,68,60,12,18,79,54,67,35,23,54,96,80,71,20,6,48,84,67,49,14,89,10,35,49,97,97,10,79,20,63,82,97,67,73,75,87,96,55,66,65,38,43,65,89,27,11,19,62,26,64];